package com.leetcode.algorithm.y22.m08.w2;

/**
 * 583. 两个字符串的删除操作
 * 
 * https://leetcode.cn/problems/delete-operation-for-two-strings/
 * 
 * @author jie.deng
 *
 */
class Question0583Solution01 {

	public int minDistance(String word1, String word2) {
		// DP状态定义
		int len1 = word1.length();
		int len2 = word2.length();
		if (len1 == 0) {
			return len2;
		}
		if (len2 == 0) {
			return len1;
		}
		// dp[i][j]表示使得 word1的前i个字符 和 word2的前j个字符 相同所需的最小步数
		int dp[][] = new int[len1 + 1][len2 + 1];
		// DP状态初始化
		for (int i = 0; i <= len1; i++) {
			dp[i][0] = i;
		}
		for (int i = 0; i <= len2; i++) {
			dp[0][i] = i;
		}

		// DP状态转移
		for (int i = 1; i <= len1; i++) {
			for (int j = 1; j <= len2; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
				}
			}
		}

		return dp[len1][len2];
	}

}